‎

Sequentially Generating Permutations in C++

Sequentially Generating Permutations in C++

There are a few cases where you'd like to iterate over all permutations of n objects.

It's interesting to note that in most cases, neither generating the full set in memory, nor iteration over it will suffice because the set is so massive, but nonetheless it's nice to have the algorithm in case there's some small-scale problem you'd want to brute force.

Here's some C++ code that will generate a list of permutations for you. It can be modified in a straightforward way to iterate instead, perhaps altered to accept a lambda function to apply to each one on generation.

#include <iostream>
#include <list>
#include <algorithm>

template<typename type_t>
std::list<std::list<type_t> > permutations  ( std::list<type_t> set ) {
  typedef std::list<type_t> oset_t;
  typedef std::list<oset_t > oset_oset_t;
  oset_oset_t result_set;
  if(set.size() == 1) {
        result_set.push_back(set);
        return result_set;
  } else {
        for(auto i=set.begin();i!=set.end();i++) {
          std::list<type_t> rest_of_list;
          std::copy(set.begin(),set.end(),std::back_inserter(rest_of_list));
          rest_of_list.remove((*i));
          std::list<std::list<type_t> > partial_result = permutations<type_t>(rest_of_list);
          for(auto p = partial_result.begin();p!=partial_result.end();p++) {
                p->push_front(*i); }
          std::copy(partial_result.begin(),partial_result.end(),std::back_inserter(result_set)); }
        return result_set; }}

int main (){
  std::list<int> S;
  for(int i=0;i<6;i++) {
        S.push_back(i); }
  std::list<std::list<int> > P = permutations<int>(S);

  for(auto i = P.begin();i!=P.end();i++) {
        for(auto j = i->begin();j!=i->end();j++) {
          std::cout<<(*j); }
        std::cout<<std::endl;
  }
}

To be honest, I'm only including this oneshot article because I wanted a quick way to test C++ syntax highlighting in the blog.

Table of Contents

Sequentially Generating Permutations in C++